package com.example.leetdemo.finash;

import java.util.Arrays;

public class Solution75 {

    public static void main(String[] args) {
        Solution75 solution75 = new Solution75();
        int[] test = new int[] {1,2,4,2,1,3};
        solution75.sortColors(test);
        for (int i = 0; i < test.length; i++) {
            System.err.print(" " + test[i]);
        }
    }

    public void sortColors(int[] nums) {
        int p = 0, q = nums.length - 1;
        qkSort(nums, p, q);
        Arrays.sort(nums);
    }
    private void  qkSort(int[] num, int p, int q) {
        if (q >= p) {
            return;
        }
        int select = num[p];
        int l = p + 1, r = q;
        while (l <= q) {
            if (num[l] < select) {
                num[l - 1] = num[l];
                l++;
            }
            if (num[r] > select) {
                r--;
            }
            if (num[l] > select && num[r] < select) {
                swap(num, l, r);
            }
        }
        num[l - 1] = select;
        qkSort(num, p, l - 1);
        qkSort(num, l, q);
    }

    private void swap(int[] num, int p, int q) {
        int swap = num[p];
        num[p] = num[q];
        num[q] = swap;
    }
}
